
import { TreeNode } from "./00_二叉搜索树BSTree";
import {btPrint} from 'hy-algokit'

class AVLTreeNode<T> extends TreeNode<T> {
    // 这里要对获取到的左节点右节点的类型进行重写，是AVLTreeNode
    left: AVLTreeNode<T> | null = null;
    right: AVLTreeNode<T> | null = null;
    parent: AVLTreeNode<T> | null = null;

    height: number = 1;

    // 获取每个节点的高度
    private getHeight(): number { 
        // 左子节点存在的话再去获得左子节点的高度
        const leftHeight = this.left? this.left.getHeight() : 0;
        const rightHeight = this.right? this.right.getHeight() : 0;
        // 找出左子节点和右子节点中较大的高度再加一就是平衡二叉树的高度
        return Math.max(leftHeight, rightHeight) + 1;
    }
    //权重: 平衡因子(左height - 右height)
    private getBalanceFactor(): number {
        const leftHeight = this.left? this.left.getHeight() : 0;
        const rightHeight = this.right? this.right.getHeight() : 0;

        return leftHeight - rightHeight;
    }

    // 直接判断当前节点是否平衡
    get isBalanced(): boolean {
        const factor = this.getBalanceFactor()
        // return factor >= -1 && factor<= 1; // -1,0,1
        // abs 是绝对值的意思
        return Math.abs(factor) <= 1
    }

    // 获取更高子节点
    public get higherChild(): AVLTreeNode<T> | null{
        const leftHeight = this.left? this.left.getHeight() : 0;
        const rightHeight = this.right? this.right.getHeight() : 0;
        if(leftHeight > rightHeight) return this.left;
        if(rightHeight > leftHeight) return this.right;
        // 正常情况下不会来到这里，但是根据规定，如果左子节点和右子节点高度一样的话
        // 如果当前当前节点是左子节点就返回左节点，如果是右子节点就返回右节点
        return this.isLeft ? this.left : this.right
    }

    // 旋转操作,右旋转
    rightRotation(){
        const isLeft = this.isLeft
        const isRight = this.isRight
        // 1、处理pivot节点,右旋转，说明左侧一定有值，
        const pivot = this.left!;
        // 让中轴点的父节点等于当前跟节点的父节点，此时可以理解为根节点之前的父节点指向了中轴点，（中轴点相当于新的根节点，不过此时this还是老的父节点）
        pivot.parent = this.parent;
        // 2、处理pivot的right（让老的根节点的左侧指向中轴点的右侧）
        // 然后老根节点的左侧是指向中轴点的右侧，可能为空。简单理解相当于连线
        this.left = pivot?.right;
        // 如果中轴点的右节点存在，则将其主动连接上老的根节点
        if(pivot.right){
            pivot.right.parent = this
        }
        // 3、处理this
        // this = pivot?.left
        //此时pivot已经上位为根节点，要让其右节点指向之前老的根节点，先主动指向他，再让其老根节点指回来（都要相互指一下）
        pivot.right = this;
        this.parent = pivot
        //4、挂载pivot

        if(!pivot.parent){ // pivot直接座位tree的跟
            // pivot.parent = this.parent
        }else if(isLeft){ // pivot作为父节点的左子节点
            pivot.parent.left = pivot;
        }else if(isRight){ // pivot作为父节点的右子节点
            pivot.parent.right = pivot;
        }
        return pivot;
    }
}

// 测试某个节点的高度

const av1Node1 = new AVLTreeNode(10)
av1Node1.left = new AVLTreeNode(8)
av1Node1.left.parent = av1Node1;
av1Node1.left.left = new AVLTreeNode(5)
av1Node1.left.left.parent = av1Node1.left;
const parent = new AVLTreeNode(12)

parent.left = av1Node1;
// 设置parent
av1Node1.parent = parent;
btPrint(parent)

av1Node1.rightRotation()
btPrint(parent)


